The present invention is in the technical field of data visualization. More specifically, the present invention is in the technical fields of graph visualization and human computer interaction (HCI).
Much information is stored as a graph or network, for example, semantic networks, social networks, and many types of biological networks. The World Wide Web can also be considered a graph, in which each web page is a node, and the hyperlinks between them are edges.
Existing visualizations of graph-based information are either too simplistic; i.e. they do not take into consideration the non-linear relationships between multiple pieces of information, for instance they select a portion of information from a graph and display it as a one-dimensional list, or said visualizations are too complex; i.e. they display the edges between pieces of information, becoming entangled when the structure is large or does not conform to a neat arrangement such as a tree or planar graph.
Many existing user interfaces use a grid format to display a set of icons representing distinct pieces of information or access points to information. The existing grid-based displays appear to be arranged either linearly or arbitrarily. Arranging the icons so that related items are closer to each other than unrelated items would help the user navigate the information. A graph is a natural data structure to represent the relationships between pieces of information, and is frequently used to do so.
Many device display libraries contain tools to display information in a two-dimensional grid format. This makes implementation of the present invention straightforward using a wide variety of display libraries.
A graph (also called a network) is defined as a plurality of nodes and a plurality of edges, in which any two nodes may be connected by an edge. In the present invention, a node contains a piece of information or an access point to information. An edge between two nodes indicates that their contents are directly related in some manner. The type of edge indicates the manner in which the nodes are related. Each edge is associated with a weight that indicates the degree of relatedness of the nodes that it connects. A subgraph is a subset of nodes and/or edges the graph. In the present invention, a subgraph may be displayed as a contiguous set of cells in the grid. A cell representing a node is called a node cell. A path is a subgraph containing a plurality of k>2 nodes connected by k−1 edges in a series, such that each node is connected with an edge to at least one other node, and no node is connected to more than two other nodes.